package arithmetic2;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

/**
 * Created by AJie on 2019/8/5
 * Function :
 * 给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
 *
 * 说明：
 *
 * 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
 *
 * 示例 1:
 * 输入: [2,2,1]
 * 输出: 1
 *
 * 链接：https://leetcode-cn.com/problems/single-number
 */
public class T_136_SingleNum {


    public static void main(String[] args) {

    }

    public static int singleNumber(int[] nums) {
//        Set<Integer> set = new HashSet<>();
//        for (int i = 0; i < nums.length; i++) {
//            int num = nums[i];
//            if (set.contains(num)) {
//                set.remove(nums[i]);
//            }else {
//                set.add(nums[i]);
//            }
//        }
//        return set.iterator().next();
//        参与运算的两个值，如果两个相应bit位相同，则结果为0，否则为1。　即：
//
//　　0^0 = 0，
//
//　　1^0 = 1，
//
//　　0^1 = 1，
//
//　　1^1 = 0
//
//　　按位异或的3个特点：
//
//　　（1） 0^0=0，0^1=1 0异或任何数＝任何数
//
//　　（2） 1^0=1，1^1=0 1异或任何数－任何数取反
//
//　　（3） 任何数异或自己＝把自己置0
        int ans = nums[0];//取第一个数
        if (nums.length > 1) {
            for (int i = 1; i < nums.length; i++) {
                ans = ans ^ nums[i];//过滤出只有一个的数
            }
        }
        return ans;


//        链接：https://leetcode-cn.com/problems/two-sum/solution/xue-suan-fa-jie-guo-xiang-dui-yu-guo-cheng-bu-na-y/
    }
}
